package algorithm;

/**
 * @author fangkun
 * @create 2022-05-19-8:41
 *
 * 645
 * 给⼀个⻓度为 N 的数组 nums，其中本来装着 [1..N] 这 N 个元素，⽆序。但是现在出现了⼀些错误，nums
 * 中的⼀个元素出现了重复，也就同时导致了另⼀个元素的缺失。请你写⼀个算法，找到 nums 中的重复元素
 * 和缺失元素的值。
 */
public class SetMismatch {

    public static void main(String[] args) {

        int[] nums = findErrorNums(new int[]{1, 2, 2, 4});

        for (int num:nums){
            System.out.println(num);
        }
    }

    static int[] findErrorNums(int[] nums){

        int n = nums.length;

        int dup = -1;

        for (int i = 0; i < n; i++) {

            // 现在的元素是从 1 开始的
            int index = Math.abs(nums[i]) - 1;

            if (nums[index] < 0)
                dup = Math.abs(nums[i]);
            else
                nums[index] *= -1;
        }

        int missing = -1;
        for (int i = 0; i < n; i++)
            if (nums[i] > 0)
                // 将索引转换成元素
                missing = i + 1;

        return new int[]{dup, missing};
    }
}
